
// Definition for a binary tree node.
class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function get_fa(root: TreeNode | null): Map<TreeNode, TreeNode | null> {
    const m = new Map();
    m.set(null, null);
    const vis_arr = [root];
    let idx = 0;
    while(idx < vis_arr.length)
    {
        const cur_node = vis_arr[idx++];
        if (cur_node == null)
            continue;
        vis_arr.push(cur_node.left);
        m.set(cur_node.left, cur_node);
        vis_arr.push(cur_node.right);
        m.set(cur_node.right, cur_node);
    }
    m.delete(null);
    return m;
}

type NodeDepthPair = {
    node: TreeNode | null;
    depth: number;
};

function get_depth(root: TreeNode | null): Map<TreeNode, number> {
    const m = new Map();
    m.set(null, null);
    const vis_arr : NodeDepthPair[] = [{node: root, depth: 0}];
    let idx = 0;
    while(idx < vis_arr.length)
    {
        const {node:cur_node, depth:cur_depth} = vis_arr[idx++];
        if (cur_node == null)
            continue;
        m.set(cur_node, cur_depth);
        vis_arr.push({node: cur_node.left, depth: cur_depth + 1});
        vis_arr.push({node: cur_node.right, depth: cur_depth + 1});
    }
    m.delete(null);
    return m;
}

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    const fa_map = get_fa(root);
    const depth_map = get_depth(root);
    if (depth_map.get(p) < depth_map.get(q))
        [p, q] = [q, p];
    while(depth_map.get(p) > depth_map.get(q))
        p = fa_map.get(p);
    while(p != q)
        p = fa_map.get(p), q = fa_map.get(q);
    return p;
};


